import bean.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode2130 {

    public static void main(String[] args) {
        System.out.println("结果：" + pairSum(ListNode.createListNodes(new int[]{1,9})));
    }

    /**
     * 思路，用慢指针找到中间节点，然后将中间节点之后的数据存到linklist里面，再从头节点和linklist的尾节点开始相加，找到最大值
     * @param head
     * @return
     */
    public static int pairSum(ListNode head) {
        int result = 0;
        ListNode low = head;
        ListNode fast = head.next;

        int num = 0;

        while (fast.next != null){
            low = low.next;
            fast = fast.next.next;
            num++;
        }

        List<ListNode> linkedList = new ArrayList<>(num);
        while (low.next != null){
            linkedList.add(low.next);
            low = low.next;
        }

//        ListNode.printNodeList(head);
//        System.out.println();
//        for (ListNode ss: linkedList){
//            System.out.print(ss.val + "  ");
//
//
//        }
//        System.out.println();

        for (int i = linkedList.size() - 1; i >= 0; i--){
            result = Math.max(result, linkedList.get(i).val + head.val);
            head = head.next;
        }

        return result;
    }
}
